from tools_algorithm import *
from sortedcontainers import SortedList


class Solution:
    def resultArray(self, nums: List[int]) -> List[int]:
        a, b = SortedList(), SortedList()
        a.add(nums[0])
        b.add(nums[1])
        ra, rb = [nums[0]], [nums[1]]
        for i in range(2, len(nums)):
            v = nums[i]
            va = a.bisect_right(v)
            vb = b.bisect_right(v)
            ga, gb = len(a) - va, len(b) - vb
            if ga < gb or (ga == gb and len(a) > len(b)):
                b.add(v)
                rb.append(v)
            else:
                a.add(v)
                ra.append(v)
        return ra + rb
